<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  
  
  <title>KMP算法详解 | Hexo</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no">
  <meta name="description" content="毒瘤算法">
<meta property="og:type" content="article">
<meta property="og:title" content="KMP算法详解">
<meta property="og:url" content="http://example.com/2021/06/06/KMP%E7%AE%97%E6%B3%95%E8%AF%A6%E8%A7%A3/index.html">
<meta property="og:site_name" content="Hexo">
<meta property="og:description" content="毒瘤算法">
<meta property="og:locale" content="en_US">
<meta property="og:image" content="https://cdn.luogu.com.cn/upload/image_hosting/z3xstmxr.png">
<meta property="og:image" content="https://cdn.luogu.com.cn/upload/image_hosting/d5h8fim8.png">
<meta property="og:image" content="https://cdn.luogu.com.cn/upload/image_hosting/r30nr5sj.png">
<meta property="article:published_time" content="2021-06-06T12:44:18.363Z">
<meta property="article:modified_time" content="2023-07-19T11:51:16.919Z">
<meta property="article:author" content="John Doe">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://cdn.luogu.com.cn/upload/image_hosting/z3xstmxr.png">
  
    <link rel="alternate" href="/atom.xml" title="Hexo" type="application/atom+xml">
  
  
    <link rel="shortcut icon" href="/favicon.png">
  
  
    
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/typeface-source-code-pro@0.0.71/index.min.css">

  
  
<link rel="stylesheet" href="/css/style.css">

  
    
<link rel="stylesheet" href="/fancybox/jquery.fancybox.min.css">

  
  
<meta name="generator" content="Hexo 6.3.0"></head>

<body>
  <div id="container">
    <div id="wrap">
      <header id="header">
  <div id="banner"></div>
  <div id="header-outer" class="outer">
    <div id="header-title" class="inner">
      <h1 id="logo-wrap">
        <a href="/" id="logo">Hexo</a>
      </h1>
      
    </div>
    <div id="header-inner" class="inner">
      <nav id="main-nav">
        <a id="main-nav-toggle" class="nav-icon"><span class="fa fa-bars"></span></a>
        
          <a class="main-nav-link" href="/">Home</a>
        
          <a class="main-nav-link" href="/archives">Archives</a>
        
      </nav>
      <nav id="sub-nav">
        
        
          <a class="nav-icon" href="/atom.xml" title="RSS Feed"><span class="fa fa-rss"></span></a>
        
        <a class="nav-icon nav-search-btn" title="Search"><span class="fa fa-search"></span></a>
      </nav>
      <div id="search-form-wrap">
        <form action="//google.com/search" method="get" accept-charset="UTF-8" class="search-form"><input type="search" name="q" class="search-form-input" placeholder="Search"><button type="submit" class="search-form-submit">&#xF002;</button><input type="hidden" name="sitesearch" value="http://example.com"></form>
      </div>
    </div>
  </div>
</header>

      <div class="outer">
        <section id="main"><article id="post-KMP算法详解" class="h-entry article article-type-post" itemprop="blogPost" itemscope itemtype="https://schema.org/BlogPosting">
  <div class="article-meta">
    <a href="/2021/06/06/KMP%E7%AE%97%E6%B3%95%E8%AF%A6%E8%A7%A3/" class="article-date">
  <time class="dt-published" datetime="2021-06-06T12:44:18.363Z" itemprop="datePublished">2021-06-06</time>
</a>
    
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 class="p-name article-title" itemprop="headline name">
      KMP算法详解
    </h1>
  

      </header>
    
    <div class="e-content article-entry" itemprop="articleBody">
      
        <p>毒瘤算法</p>
<h1 id="1-前置约定"><a href="#1-前置约定" class="headerlink" title="-1.前置约定"></a>-1.前置约定</h1><p>如非特殊说明，以下文字中$T$代表主串，$P$代表模式串，$m$代表主串长度，$n$代表模式串长度</p>
<p><strong>真前缀</strong> 一个字符串除了它本身之外的前缀。例如，<code>moo</code> 是 <code>moon</code> 的真前缀，<code>moon</code> 却不是。<strong>真后缀</strong>同理。</p>
<p><strong>“border”</strong> 如果字符串 $a$ 既是 $b$ 的真前缀，又是 $b$ 的真后缀，那么我们说 $a$ 是 $b$ 的 border。    </p>
<h1 id="0-什么是KMP？"><a href="#0-什么是KMP？" class="headerlink" title="0.什么是KMP？"></a>0.什么是KMP？</h1><blockquote>
<p>KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度$O(m+n)$。——摘自百度百科</p>
</blockquote>
<p>简而言之，它可以在 $O(m+n)$ 的时间复杂度之内在主串 $T$ 中找到所有模式串 $P$，非常优秀。</p>
<h1 id="1-正文"><a href="#1-正文" class="headerlink" title="1.正文"></a>1.正文</h1><h2 id="1-1-求-next-数组"><a href="#1-1-求-next-数组" class="headerlink" title="1.1.求$next$数组"></a>1.1.求$next$数组</h2><p>KMP算法需要求一个“$next$数组”，<strong>$next<em>i$= $P</em>{1…i}$ 最大的border的长度</strong></p>
<p>注意到border有一些很好的性质，例如：</p>
<ol>
<li>传递性。如果 $a$ 是 $b$ 的 border， $b$ 是 $c$ 的 border，那么 $a$ 是 $c$ 的 border。</li>
<li><strong>如果 $a$ 是 $s$ 的 border,那么比 $a$ 小的最大 $s$ 的 border 一定是 $a$ 的最大 border。</strong> 换句话说，把 $s$ 的所有 border 从大到小排序，那么在后面的 border 也是在前面的 border 的 border。</li>
</ol>
<p>根据上面两个性质可以推出这样一个有趣的结论：<strong>如果知道 $next_{1…i-1}$ ，就可以找出字符串的所有 border ！</strong></p>
<p>所以 $next<em>i$ 、 $next</em>{next<em>i}$ 、 $next</em>{next<em>{next_i}}$ ……是所有字符串 $P</em>{1..i}$ 的 border 的长度。<del>老套娃了</del></p>
<p>于是我们可以根据这个性质递推出 $next$ 数组。</p>
<p>根据 $next$ 数组的定义，显然有 $next_1=0$。</p>
<p>假设 $next<em>1$ 到 $next</em>{i-1}$都已经被求出来了。如果当前要求 $next<em>i$ ，我们只需让 $j$ 依次等于 $next</em>{i-1}$ 、 $next<em>{next</em>{i-1}}$ 、 $next<em>{next</em>{next<em>{i-1}}}$…… （$P</em>{1…i-1}$ 所有 border 的长度），因为 border 的定义， $P<em>{1…j}==P</em>{i-j…i-1}$ 总是成立，所以如果 $P<em>{j+1}==P</em>{i}$ ，就说明 $P<em>{1…j+1}==P</em>{i-j…i}$ ，即找到了 $P_{1..i}$ 的一个 border。</p>
<p><img src="https://cdn.luogu.com.cn/upload/image_hosting/z3xstmxr.png" alt=""></p>
<p>不难看出，最先找到的 border 一定是最大的 border ,即 $next_i$。</p>
<p>于是可以写出求 $next$ 数组的代码：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line">next[<span class="number">1</span>]=<span class="number">0</span>;</span><br><span class="line"><span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">2</span>;i&lt;=n;i++)&#123;</span><br><span class="line">    <span class="type">int</span> j=next[i<span class="number">-1</span>];</span><br><span class="line">    <span class="keyword">while</span>(j&gt;<span class="number">0</span>&amp;&amp;p[i]!=p[j+<span class="number">1</span>])&#123;</span><br><span class="line">        j=next[j];</span><br><span class="line">    &#125;<span class="comment">//让j依次等于P[1...i-1]的所有border</span></span><br><span class="line">    <span class="keyword">if</span>(p[i]==p[j+<span class="number">1</span>])&#123;</span><br><span class="line">        j++;</span><br><span class="line">    &#125;</span><br><span class="line">    next[i]=j;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="1-2-匹配"><a href="#1-2-匹配" class="headerlink" title="1.2.匹配"></a>1.2.匹配</h2><p>先来看看暴力算法的思路。</p>
<p><img src="https://cdn.luogu.com.cn/upload/image_hosting/d5h8fim8.png" alt=""></p>
<p>然而我们可以发现，它的时间复杂度甚至达到了$O(mn)$。在暴力算法中，如果发生了失配（即匹配到半路发现有一个字符不相等），只能把模板串往后移1位再重新开始匹配。这样做效率实在太低了，有什么办法优化吗？</p>
<p>当然有！</p>
<p>如果发生下列情况：</p>
<p><img src="https://cdn.luogu.com.cn/upload/image_hosting/r30nr5sj.png" alt=""></p>
<p>可以直接把模板串后移 $j-next_j$ 位，即令 $j$ 赋值为 $next_j$。如果仍然失配，就重复以上过程，直到匹配成功为止，然后进行下一轮匹配。</p>
<p>这个东西跟求 $next$ 数组思想类似，代码肯定也类似啦</p>
<p>代码：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>,j=<span class="number">0</span>;i&lt;=m;i++)&#123;</span><br><span class="line">    <span class="keyword">while</span>(j&gt;<span class="number">0</span>&amp;&amp;t[i]!=p[j+<span class="number">1</span>])&#123;</span><br><span class="line">        j=next[j];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>(t[i]==p[j+<span class="number">1</span>])&#123;</span><br><span class="line">        j++;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>(j==n)&#123;<span class="comment">//匹配成功！OHHHHHHHHHHHHHH！</span></span><br><span class="line">        cout&lt;&lt;i-j+<span class="number">1</span>&lt;&lt;endl;<span class="comment">//输出位置</span></span><br><span class="line">        j=next[j];<span class="comment">//不能躺在功劳簿上睡大觉，重新开始下一轮匹配！</span></span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="1-3-时间复杂度"><a href="#1-3-时间复杂度" class="headerlink" title="1.3 时间复杂度"></a>1.3 时间复杂度</h2><p>匹配过程的时间复杂度乍一看很高，因为它有两重循环。实际上，内层循环的执行次数一定不超过 $m$ 次，因为每一次内层循环至少会让 $j$ 减少 $1$，每一次外层循环至多会让 $j$ 加上 $1$，所以内层循环执行次数一定不超过外层循环，即 $m$ 次。所以，不难看出整个匹配过程的时间复杂度为 $\Theta(m)$ 。</p>
<p>求 $next$ 数组过程好像不能通过以上方法分析，然而它还有一种等价写法，也是我常用的写法：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line">next[<span class="number">1</span>]=<span class="number">0</span>;</span><br><span class="line"><span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">2</span>,j=<span class="number">0</span>;i&lt;=n;i++)&#123;</span><br><span class="line">    <span class="keyword">while</span>(j&gt;<span class="number">0</span>&amp;&amp;p[i]!=p[j+<span class="number">1</span>])&#123;</span><br><span class="line">        j=next[j];</span><br><span class="line">    &#125;<span class="comment">//让j依次等于P[1...i-1]的所有border</span></span><br><span class="line">    <span class="keyword">if</span>(p[i]==p[j+<span class="number">1</span>])&#123;</span><br><span class="line">        j++;</span><br><span class="line">    &#125;</span><br><span class="line">    next[i]=j;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>这样，也不难看出求 $next$ 数组过程的时间复杂度为 $\Theta(n)$</p>
<p>综上，整个 KMP 算法的时间复杂度为 $\Theta(m+n)$，非常快。</p>
<h1 id="2-总结"><a href="#2-总结" class="headerlink" title="2.总结"></a>2.总结</h1><p>KMP 算法的精髓在于废旧信息的重新利用和发掘问题性质，<del>同时这也是一个非常烧脑的算法，</del> 非常巧妙。</p>
<p>再附赠一份能通过<a target="_blank" rel="noopener" href="https://www.luogu.com.cn/problem/P3375">模板题</a>的代码：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstring&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="meta">#<span class="keyword">define</span> MAXN 1000000</span></span><br><span class="line"><span class="type">int</span> nxt[MAXN + <span class="number">5</span>], n, m;</span><br><span class="line"><span class="type">char</span> t[MAXN + <span class="number">5</span>], p[MAXN + <span class="number">5</span>];</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">    ios::<span class="built_in">sync_with_stdio</span>(<span class="literal">false</span>);</span><br><span class="line">    cin &gt;&gt; t + <span class="number">1</span> &gt;&gt; p + <span class="number">1</span>;</span><br><span class="line">    m = <span class="built_in">strlen</span>(t + <span class="number">1</span>);</span><br><span class="line">    n = <span class="built_in">strlen</span>(p + <span class="number">1</span>);</span><br><span class="line">    nxt[<span class="number">1</span>] = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">2</span>; i &lt;= n; i++) &#123;</span><br><span class="line">        <span class="type">int</span> j = nxt[i - <span class="number">1</span>];</span><br><span class="line">        <span class="keyword">while</span> (j &gt; <span class="number">0</span> &amp;&amp; p[i] != p[j + <span class="number">1</span>]) &#123;</span><br><span class="line">            j = nxt[j];</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (p[i] == p[j + <span class="number">1</span>]) &#123;</span><br><span class="line">            j++;</span><br><span class="line">        &#125;</span><br><span class="line">        nxt[i] = j;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">1</span>, j = <span class="number">0</span>; i &lt;= m; i++) &#123;</span><br><span class="line">        <span class="keyword">while</span> (j &gt; <span class="number">0</span> &amp;&amp; t[i] != p[j + <span class="number">1</span>]) &#123;</span><br><span class="line">            j = nxt[j];</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (t[i] == p[j + <span class="number">1</span>]) &#123;</span><br><span class="line">            j++;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (j == n) &#123;</span><br><span class="line">            cout &lt;&lt; i - j + <span class="number">1</span> &lt;&lt; endl;</span><br><span class="line">            j = nxt[j];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">1</span>; i &lt;= n; i++) &#123;</span><br><span class="line">        cout &lt;&lt; nxt[i] &lt;&lt; <span class="string">&#x27; &#x27;</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
      
    </div>
    <footer class="article-footer">
      <a data-url="http://example.com/2021/06/06/KMP%E7%AE%97%E6%B3%95%E8%AF%A6%E8%A7%A3/" data-id="clk9o8ln000028wi5fzf985xs" data-title="KMP算法详解" class="article-share-link"><span class="fa fa-share">Share</span></a>
      
      
      
    </footer>
  </div>
  
    
<nav id="article-nav">
  
    <a href="/2021/07/29/%E5%B1%B1%E6%B5%B7%E7%BB%8F%20%E9%A2%98%E8%A7%A3/" id="article-nav-newer" class="article-nav-link-wrap">
      <strong class="article-nav-caption">Newer</strong>
      <div class="article-nav-title">
        
          山海经 题解
        
      </div>
    </a>
  
  
    <a href="/2020/08/29/%20%E4%BF%A1%E5%A5%A5%E9%A2%98%E5%BA%93%EF%BC%88OI%E9%A2%98%E5%BA%93%EF%BC%898%E6%9C%88%E6%9C%88%E8%B5%9BT1%E9%A2%98%E8%A7%A3%20%E5%B9%82%E6%AC%A1%E6%95%B0/" id="article-nav-older" class="article-nav-link-wrap">
      <strong class="article-nav-caption">Older</strong>
      <div class="article-nav-title">信奥题库（OI题库）8月月赛T1题解 幂次数</div>
    </a>
  
</nav>

  
</article>


</section>
        
          <aside id="sidebar">
  
    

  
    

  
    
  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Archives</h3>
    <div class="widget">
      <ul class="archive-list"><li class="archive-list-item"><a class="archive-list-link" href="/archives/2023/07/">July 2023</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2022/10/">October 2022</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2022/05/">May 2022</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2022/02/">February 2022</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2022/01/">January 2022</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2021/08/">August 2021</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2021/07/">July 2021</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2021/06/">June 2021</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2020/08/">August 2020</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Recent Posts</h3>
    <div class="widget">
      <ul>
        
          <li>
            <a href="/2023/07/17/%E5%86%B3%E7%AD%96%E5%8D%95%E8%B0%83%E6%80%A7%E4%BC%98%E5%8C%96DP%20%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0%20AND%20P4767%20%E3%80%8CIOI2000%E3%80%8D%20%E9%82%AE%E5%B1%80%20%E9%A2%98%E8%A7%A3/">决策单调性优化DP 学习笔记 AND P4767 「IOI2000」 邮局 题解</a>
          </li>
        
          <li>
            <a href="/2022/10/30/CSP-S%202022%20%E6%B8%B8%E8%AE%B0/">CSP-S 2022 游记</a>
          </li>
        
          <li>
            <a href="/2022/05/29/%E6%96%9C%E7%8E%87%E4%BC%98%E5%8C%96%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%20%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/">斜率优化动态规划 学习笔记</a>
          </li>
        
          <li>
            <a href="/2022/05/22/PKUSC%E4%B8%80%E5%8F%A5%E8%AF%9D%E6%B8%B8%E8%AE%B0/">PKUSC一句话游记</a>
          </li>
        
          <li>
            <a href="/2022/05/18/%E7%9C%81%E9%80%89%E6%B8%B8%E8%AE%B0%EF%BC%9F%E7%9C%81%E9%80%89%E6%B8%B8%E5%AF%84%EF%BC%81/">省选游记？省选游寄！</a>
          </li>
        
      </ul>
    </div>
  </div>

  
</aside>
        
      </div>
      <footer id="footer">
  
  <div class="outer">
    <div id="footer-info" class="inner">
      
      &copy; 2023 John Doe<br>
      Powered by <a href="https://hexo.io/" target="_blank">Hexo</a>
    </div>
  </div>
</footer>

    </div>
    <nav id="mobile-nav">
  
    <a href="/" class="mobile-nav-link">Home</a>
  
    <a href="/archives" class="mobile-nav-link">Archives</a>
  
</nav>
    


<script src="/js/jquery-3.6.4.min.js"></script>



  
<script src="/fancybox/jquery.fancybox.min.js"></script>




<script src="/js/script.js"></script>





  </div>
</body>
</html>